#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define ARRAY_SIZE 10
#define NUMBER_RANGE 100

void counting_sort(int arr[],int len,int ret[],int range) {

    int count[NUMBER_RANGE+1];
    int i=0;
    for(i=0;i<=range;i++) {
	count[i]=0;	
    }
    for(i=1;i<=len;i++) {
	count[arr[i]]++;
    }
	
    for(i=1;i<=range;i++) {
	count[i]+=count[i-1];	
    }
    for(i=len;i>0;i--) {
	ret[count[arr[i]]]=arr[i];
	count[arr[i]]--;
    }

}

int main(){
    int i = 0;
    int arr[ARRAY_SIZE+1];
    int ret[ARRAY_SIZE+1];

    srand((unsigned)time(NULL));
    for(i=1;i<=ARRAY_SIZE;i++){
        arr[i] = rand()%NUMBER_RANGE;
    }

    printf("sort array  [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
    counting_sort(arr,ARRAY_SIZE,ret,NUMBER_RANGE);

    printf("sort result [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",ret[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");

    return 0;
}

